The invention relates to Content Addressable Memories (CAM) and circuits for detecting multiple matches therein.
A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data being stored within a given memory location) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory search on a RAM, the user supplies the address and gets back the data stored in that address (location).
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address, or the data can be written into a first empty memory location. Once information is stored in a memory location, it is found doing a memory search by comparing every bit in any memory location with every bit of data in a comparand register circuit. When the content stored in the CAM memory location does not match the data placed in the comparand register, the CAM device returns a no match indication. When the content stored in the CAM memory location matches the data placed in the comparand register, the CAM device returns a match indication. In addition, the CAM returns the identification of the address location in which the matching data is stored. Thus, with a CAM, the user supplies the data and gets back an indication of an address where a matching data is stored in the memory.
Locally, CAMs perform an exclusive-NOR (XNOR) function, so that a match is indicated only if both the stored bit and the corresponding input bit are the same state. CAMs are designed so that any number, or all of the memory locations may be simultaneously searched for a match with incoming data. In certain cases, data in more than a single location in the memory matches the input data, and such condition of multiple simultaneous matches must be detected and reported. However, circuitry for detecting multiple matches in a CAM memory generally is large and complex, and grows exponentially with the number of data words in the memory. Also, the switching time is impeded because of the parasitic capacitance associated with the complex logic. Thus, there is a need for a multiple match detector having increased switching speed, yet reduced circuit complexity.
In one aspect, the invention provides a circuit for detecting multiple matches in a content addressable memory including a plurality of input pins where is are connected to a match line of the content addressable memory; a plurality of transistors connected to the input pins and logically arranged to detect a multiple match condition; a current source transistor for controlling the current through the plurality of transistors; and a current sensing detector connected to the plurality of transistors for outputting a signal indicating that a multiple match condition has been detected.
In an additional aspect, a portion of the plurality of transistors are connected in parallel to achieve a logical xe2x80x98ORxe2x80x99 condition; and a portion of the plurality of transistors are connected in series to achieve a logical xe2x80x98ANDxe2x80x99 condition. In yet another aspect, a plurality of OR gates are connected to the input line of a multiple match signal. Additional aspects of the present invention include a method for operating the above components.